Masala #0916

Xotira 32 MB Vaqt 1500 ms Qiyinchiligi 35 %
14

  

Metrodan foydalanish

Metro \(N\) ta bekatdan va \(M\) ta bekatlarni o‘zaro bog‘lovchi yo‘llardan tashkil topgan. Agar \(u\) va \(v\) bekatlar orasida yo‘l mavjud bo‘lsa, unda \(u\) dan \(v\) ga yoki \(v\) dan \(u\) ga 1 daqiqada yetib borsa bo‘ladi.

Toshkent shahriga ko’chib kelgan Davlatbek metrodan ko‘p foydalana boshladi. Xususan bugun, Davlatbek \(Q\) marta metrodan foydalanmoqchi. \(i\)-foydalanishida \(a_i\) bekatdan \(b_i\) bekatga borishi haqida aniq reja qildi. Agar metroni kutish va metro almashtirish vaqti inobatga olinmasa, Davlatbek har bir metrodan foydalanishida minimal necha daqiqa vaqtini metroda o‘tkazadi? Agar \(i\)-foydalanishi imkonsiz bo‘lsa −1 chiqaring.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(N\) va \(M\) \((2≤N≤300,1≤M≤ \dfrac{N(N−1)}{2})\) bekatlar soni va bekatlar orasidagi yo‘llari soni kiritiladi.

Keyingi \(M\) ta qatorda ikkitadan butun son - \(u_i\) va \(v_i(1 ≤ v_i, u_i ≤ N )\) kiritiladi. Bu \(u_i\) va \(v_i\) bekatlar orasida yo‘l mavjud ekanligini anglatadi.

So‘ng yangi qatorda yagona butun son - \(Q(1 ≤ Q ≤ 300)\) Davlatbekning bugun metrodan foydalanishlari soni kiritiladi.

Keyingi \(Q\) ta qatorda ikkitadan butun son - \(a_i\) va \(b_i(1 ≤ a_i, b_i ≤ N )\), \(i\)-foydalanishdagi kirish va chiqish bekatlari kiritiladi.


Chiquvchi ma'lumotlar:

\(i\)-foydalanish uchun \(i\)-qatorda \(a_i\) bekatdan \(b_i\) bekatga yetib borish uchun ketadigan minimal vaqtni chiqaring. Buning imkoni bo‘lmasa \(−1\) chiqaring.


Misollar
# input.txt output.txt
1
2 1
1 2
2
1 2
1 2
1
1
2
3 3
1 3
1 2
2 3
5
2 1
1 2
3 2
2 1
2 2
1
1
1
1
0
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin